#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE  10
typedef int Elemtype;

typedef struct LinkNode
{
  Elemtype data;
  struct LinkNode *next;
}LinkNode,*LinkList;

//尾插法创建链表
void create(LinkList * L,Elemtype arr[],int length){
      (*L) = (LinkNode*)malloc(sizeof(LinkNode));
      (*L)->next = NULL;
      int cnt = 0;
      LinkNode* pCur = (*L);
      while (cnt< length)
      {
      LinkNode *pNode = (LinkNode*)malloc(sizeof(LinkNode));
      pNode->data = arr[cnt++];
      pNode->next = NULL;
      pCur->next = pNode;
      pCur = pCur->next;
      }
}

//尾插法创建链表
void create02(LinkList * L,Elemtype arr[],int length){
      (*L) = (LinkNode*)malloc(sizeof(LinkNode));
      (*L)->next = NULL;
      int cnt = 0;
      LinkNode* pCur = (*L);
      while (cnt< length)
      {
      LinkNode *pNode = (LinkNode*)malloc(sizeof(LinkNode));
      pNode->data = arr[cnt++];
      pNode->next = pCur->next ;
      pCur->next = pNode;
     
      }
}
#define INF -999999
//求最大整数
int Max(LinkNode* pNode){
   if(pNode == NULL){
      return INF;
   }
   int res = pNode->data > Max(pNode->next) ? pNode->data:Max(pNode->next);
   return res;
}
//求节点数
int Nodes(LinkNode* pNode){
   if(pNode == NULL){
      return 0;
   }
   int res = Nodes(pNode->next) +1;
   return res;
}
//求和
int Sum(LinkNode* pNode){
   if(pNode == NULL){
      return 0;
   }
   int res = Sum(pNode->next) + pNode->data;
   return res;
}
//求第i个数据节点
LinkNode * findIth(LinkList L,int i){
   int cnt = 0;
   LinkNode *pNode = L;
   while (pNode->next!=NULL)
   {
      cnt++;
      if(i == cnt){
         return pNode->next;
      }
      pNode = pNode->next;
   }
}

//在第i个数据节点前插入一个元素e
void insertBeforeIth(LinkList L,int i,Elemtype e){
   int cnt = 0;
   LinkNode *pNode = L;
   while (pNode->next!=NULL)
   {
      cnt++;
      if(i == cnt){
         LinkNode* pNew = (LinkNode*)malloc(sizeof(LinkNode));
         pNew->data = e;
         pNew->next = pNode->next;
         pNode->next = pNew;
         break;
      }
      pNode = pNode->next;
   }
}

//求倒数第m个位置节点并输出
void getData(LinkList L,int m){
   LinkNode*pNode = L->next;
   LinkNode *pCur = L->next;
   int cnt = 1;
   while(pNode!=NULL){
      if(cnt == m+1){
         break;
      }
      pNode = pNode->next;
      cnt++;
   }//说明pnode走到了m+1位置，可以和pcur同步双指针一起走
   while (pNode!=NULL)
   {
      pNode = pNode->next;
      pCur = pCur->next;
   }
   printf("the -mth is %d\n",pCur->data);

}


//求第i个数据节点的前一节点
LinkNode * getPre(LinkList L,int i){
   int cnt = 0;
   LinkNode *pNode = L;
   while (pNode->next!=NULL)
   {
      cnt++;
      if(i == cnt){
         return pNode;
      }
      pNode = pNode->next;
   }
}


void  print(LinkList L){
   LinkNode*pNode  = L->next;
   while (pNode!=NULL)
   {
      printf(" %d ",pNode->data);
      pNode = pNode->next;
   }
   printf("\n");
   
}

//两表移植问题
void operateAandB(LinkList A,LinkList B,int j ,int len){

   //增加头节点
   LinkNode*pLa = (LinkNode*)malloc(sizeof(LinkNode));
   LinkNode*pLb = (LinkNode*)malloc(sizeof(LinkNode));
   pLa->next = A;
   pLb->next = B;
//求用到的前继节点lapre，lbpre，j+len-1,
   LinkNode* Lapre = getPre(pLa,j);
   LinkNode* Lbpre = getPre(pLb,j);
   LinkNode* Lalength = getPre(pLa,j+len-1)->next;
   //记录下ja
   LinkNode *p = Lapre->next;
   //移动
   Lapre->next = Lalength->next;
   Lalength->next = Lbpre->next;
   Lbpre->next = p;

   print(pLa);
   print(pLb);
   free(pLa);
   free(pLb);
   pLa = NULL;
   pLb = NULL;
}
//求前半部分和后半部分是否对称
int isSym(LinkList L,int n){
   int cnt=0;
   LinkNode*pNode = L;
   while (pNode->next !=NULL)
   {  cnt++;
     if(cnt == n/2){
         break;
     }
     pNode = pNode->next;
   }
   //找到了第n/2个节点:  pNode->next
   LinkNode* pFront = L->next;
   LinkNode*pLast = NULL;
   if (n % 2==0)
   {
     pLast = pNode->next->next;
   }else{
     pLast = pNode->next->next->next;
   }
   while (pLast!=NULL)
   {
      if(pFront->data!=pLast->data){
            return 0;
      }
     pLast = pLast->next;
     pFront = pFront->next;
   }
   return 1;
}
//删除非递减重复元素
 void deleteSimilar(LinkList L){
   LinkNode*pre = L;
   LinkNode*pCur = L->next;
   while (pCur!=NULL)
   {
     if(pre!=L && pre->data == pCur->data){
      //删除
      pre->next = pCur->next;
      free(pCur);
      pCur = pre->next;
     }else{
     pre = pCur;
     pCur = pCur->next;
     }
   }
 }
//非递减，统计比x小的元素个数    1,2,2,3，
int lessNodes(LinkList L,Elemtype x){
   int cnt = 0;
   LinkNode*pre = L;
   LinkNode*pCur = L->next;  
   while (pCur!=NULL && pCur->data < x)
   {
     //不是重复的
     if(pre==L || pre->data != pCur->data ){
         cnt++;
         pre = pCur;
         pCur = pCur->next;
     }else{
         pCur = pCur->next;
     }
     
   }
   printf(" the num is %d\n ",cnt);
    return cnt;
}
//删除非递减单链表La中La与非递减表Lb相同的元素
void deleteAandBSame(LinkList La,LinkList Lb){
   LinkNode *pre = La;
   LinkNode *paCur= La->next;
   LinkNode *pbCur = Lb->next;

   while(paCur!=NULL && pbCur!=NULL){
      if(paCur->data > pbCur->data){
            pbCur = pbCur->next;
      }else if(paCur->data < pbCur->data){
            pre = paCur;
            paCur = paCur->next;
      }else{
            //相等所以删除操作
            pre->next = paCur->next;
            free(paCur);
            paCur = pre->next;
      }
   }

}
//在表Lc中删除同时出现在La和Lb中的所有元素
/**
 * 寻找两个链表中相同的元素
 *    最小值，在等于时候操作
 * 在C中寻找元素并删除
 */
void deleteAandBandCSame(LinkList La,LinkList Lb,LinkList Lc){
   LinkNode *paCur = La->next;
   LinkNode *pbCur= Lb->next;
   LinkNode *pre = Lc;
   LinkNode *pcCur = Lc->next;

   while (paCur && pbCur && pcCur)
   {
      if(paCur->data > pbCur->data){
            pbCur = pbCur->next;
      }else if(paCur->data < pbCur->data){
            paCur = paCur->next;
      }else{
            //找到了A和B的相同的元素,仅删除一次
            while (pcCur!=NULL && paCur->data >= pcCur->data)
            {
               if(paCur->data == pcCur->data){
                       //删除
                     pre->next = pcCur->next;
                     free(pcCur);
                     pcCur = pre->next;
                     break;
               }
               pre = pcCur;
               pcCur = pcCur->next;
            }
            paCur = paCur->next;
            pbCur = pbCur->next;
      }
   }
}
//去重尾插
void inertTail(LinkList *LcNode,LinkNode *pNode){
   if((*LcNode)->data == pNode->data){
      return;
   }


   pNode->next = NULL;
   (*LcNode)->next = pNode;



   (*LcNode) = (*LcNode)->next;
}

//将A表和B表合并成C表并去重
void merge(LinkList La,LinkList *Lb,LinkList *Lc){

   LinkNode* paCur = La->next;
   LinkNode* pbCur = (*Lb)->next;
   *Lc = La;
   LinkNode *pcCur= *Lc;

   //因为b表头不用，合并成c之后，只用了a的表头，所以释放掉b表头
   free(*Lb);
   (*Lb) = NULL;

   while (paCur!=NULL && pbCur !=NULL)
   {
      if(paCur->data < pbCur->data){
            //把a的当前节点插入表c
            LinkNode*tempNode = paCur->next;
            //把a的当前节点插入表c
            /**
             * 判断 a和c的值是否相同  
             *    如果相同，那么不插入
             *    如果不同，说明可以插入，执行尾插步骤，并让pccur往后移动一位
             * 这里的尾插就正常的尾插   pNode->next = NULL; (*LcNode)->next = pNode;
             */
           inertTail(&pcCur,paCur); //因为要调用函数，且函数调用之后pccur要变化，所以传地址
           paCur = tempNode;
      }else if(paCur->data > pbCur->data){
            //把b的当前节点插入表c
            LinkNode*tempNode = pbCur->next;
            //把b的当前节点插入表c
           inertTail(&pcCur,pbCur);
           pbCur = tempNode;
      }else{
         //选一个插入，然后一起移动
          //把a的当前节点插入表c
            LinkNode*tempNode01 = paCur->next;
            LinkNode*tempNode02 = pbCur->next;
           inertTail(&pcCur,paCur);
           paCur = tempNode01;
           free(pbCur);
           pbCur = tempNode02;
      }
   }
   while (paCur!=NULL)
   {
        LinkNode*tempNode = paCur->next;
            //把a的当前节点插入表c
           inertTail(&pcCur,paCur);
           paCur = tempNode;
   }
   while (pbCur!=NULL)
   {
       //把b的当前节点插入表c
            LinkNode*tempNode = pbCur->next;
            //把b的当前节点插入表c
           inertTail(&pcCur,pbCur);
           pbCur = tempNode;
   }
   }
//递增单链表删除属于min-max的元素
void deleteNodes(LinkList L,int min ,int max){
   LinkNode *pre = L;
   LinkNode *pCur = L->next;
   while (pCur!=NULL && pCur->data <= max)
   {
      if(pCur->data >= min ){
            pre->next = pCur->next;
            free(pCur);
            pCur = pre->next;
      }else{
         pre = pCur;
         pCur = pCur->next;
      }
   }
}

//链表的冒泡排序
void bubbleSort(LinkList L){
//对每轮一直执行比较和交换的操作，知道这轮不交换位置
while(1){
   int isExchange = 0;
   LinkNode *pCur = L->next;
   while (pCur->next!=NULL)
   {
     if(pCur->data >pCur->next->data){
         Elemtype temp = pCur->data;
         pCur->data =pCur->next->data ;
         pCur->next->data = temp;
         isExchange = 1;
     }
     pCur = pCur->next;
   }
   if(!isExchange){
      break;
   }
}
}

void insertSort(LinkList L){
   LinkNode* pCur = L->next; //指向待排序节点
   L->next = NULL;
   while (pCur!=NULL)
   {
     //使用双指针来找位置，如果去重就是比较找到位置之后的pre的值和待插入节点的值是否相等，如果
     //相等就删除该待插入节点
     LinkNode *pre = L;
     LinkNode* pL = L->next; //有序子序列的第一个数据节点
     while(pL!=NULL){
      //找插入位置
         if(pL->data > pCur->data){
            break;
         }
         pre= pL;
         pL = pL->next;
     }
     //保证待插入序列要之后能继续访问
     LinkNode *pNode = pCur;
     pCur = pCur->next;

      // 1.不重复 2.有序子序列无数据节点或者已经是最小的了
     if(pre == L || pre->data != pNode->data){
         pNode->next = pL;
         pre->next = pNode;
     }else{
      //重复了
      free(pNode);
     }
   }
   

}

//把小于x移动到x之前，大于x移动到x之后
void move(LinkList L,Elemtype x){
   LinkNode *pCur = L->next;
   L->next = NULL;

   //定义一个虚拟节点，便于之后插入等所有的节点插入之后，将该节点删掉
   LinkNode *pX = (LinkNode*)malloc(sizeof(LinkNode));
   pX->next = NULL;
   pX->data =x; 
   //先把虚拟节点插入结果链表中，定义一个prex指针，始终指向虚拟节点的前驱
   L->next = pX;
   LinkNode * preX = L;
   LinkNode*pTail = pX;
   //对待处理数据节点进行挨个遍历，比较和x的大小关系
   while (pCur!=NULL)
   {
      LinkNode *pNode = pCur;
      pCur = pCur->next;
   if(pNode->data < x){
//小于x，在虚拟节点前面，使用头插
   pNode->next = L->next;
   L->next = pNode;
   if(preX == L){
      preX = preX->next;
   }
   }else if(pNode->data > x){
//大于x，使用尾插在虚拟节点的后面,使用到一个尾指针始终指向最后一个元素
   pNode->next = NULL;
   pTail->next = pNode;
   pTail = pNode;
   }else{
//等于x，使用prex指针把真正的x节点放在虚拟x前面
   preX->next = pNode;
   pNode->next = pX;
   preX = preX->next;
   }
   }
   //删除虚拟节点
  preX->next = pX->next;
}

//判断Lb(短链)是不是La（长链）的子链
int isSubLink(LinkList La,LinkList Lb){
   //定义pLa,pLb,start，start一直指向子链的开始
   LinkNode *pLa = La->next;
   LinkNode *pLb = Lb->next;
   LinkNode *start = pLa;

   //当a和b有一个遍历完就结束了
   while (pLa!=NULL && pLb!=NULL)
   {
     if(pLa->data == pLb->data){
         pLa =  pLa->next;
         pLb = pLb->next;
     }else{
      start = start ->next ;//下一个子链的开始和当前子链开始相邻
      pLa = start;
      pLb = Lb->next;
     }
   }
   //如果b先走完，说明都匹配，是子链  //如果a先走完，没有适配的，不是子链
   if(pLb == NULL){
      return 1;
   }
   return 0;
  
}

//求链表的数据节点的个数/链表的长度
int getLen(LinkList L){
   LinkNode *pNode = L->next;
   int len = 0;
   while (pNode!=NULL)
   {  
      len++;
      pNode = pNode->next;
   }
   return len;
}
//求共享节点的位置
LinkNode * getSharedNode(LinkList La,LinkList Lb){
   LinkNode *pLa = La->next;
   LinkNode *pLb = Lb->next;
   
   //求长度
   int lenA = getLen(La);
   int lenB = getLen(Lb);
   int cnt = 0;
   if(lenA > lenB){
      //长链长度要先往后走差值个距离
      
      while (cnt < (lenA - lenB))
      {
         pLa = pLa->next;
         cnt++;
      }
   }else{
      while (cnt < (lenB - lenA))
      {
         pLb = pLb->next;
         cnt++;
      }
   }
   while (pLa!=pLb)
   { //同时遍历，若指针值相等就返回
      pLb = pLb->next;
      pLa = pLa->next;
   }
   return pLa;
}
//转换Ln为Lt
void convertLinkList(LinkList L,int n){
   LinkNode * preNode = L->next;
   LinkNode* pLastNode = NULL; //后半段的开始
  
   int cnt = 0;
   LinkNode *pCur = L;
    // 需要找到后半段的开始
   while (pCur->next!=NULL)
   {
      cnt++;
      if(cnt > n/2){
           break; 
      }
     pCur = pCur->next;
   }
   pLastNode = pCur->next;
   //将后半段进行逆置（头插）
   L->next = NULL;
   while (pLastNode!=NULL)
   {
      LinkNode * pNode = pLastNode;
      pLastNode = pLastNode->next;
      pNode->next = L->next;
      L->next = pNode;
   }
   pLastNode = L->next;//拿到需要依次插入的后半段的开始
   //从前半段和后半段依次插入到头结点后面（尾插）
   L->next = NULL;
   pCur = L;//最后一个数据节点
   while (pLastNode!=NULL && preNode != NULL)
   {  //一个循环插入一对
      LinkNode * pNode = preNode;
      preNode = preNode->next;
      pCur->next = pNode;
      pNode->next = NULL;
      pCur = pNode;
      pNode = pLastNode;
      pLastNode = pLastNode->next;
      pCur->next = pNode;
      pNode->next = NULL;
      pCur = pNode;
   }
   //如果有剩余的就全都继续插入,一定只有后半段多一个
   pCur->next = pLastNode;
}
//构建一个带头结点的循环单链表
void createCircleList(LinkList *L,Elemtype arr[],int length){
      int cnt = 0;
      (*L) =  (LinkNode *)malloc(sizeof(LinkNode));
      (*L)->next = (*L);
      while (cnt < length)
      {
        LinkNode *pNode = (LinkNode *)malloc(sizeof(LinkNode));
        pNode->data = arr[cnt++];
        pNode->next = (*L)->next;
        (*L)->next = pNode;
      }
}
//打印带头结点的循环单链表
void printCLink(LinkList L){
   LinkNode *pNode = L->next;
   while (pNode!=L)
   {
     printf(" %d ",pNode->data);
     pNode = pNode->next;
   }
   printf("\n");
   
}
//打印带头结点的循环单链表
void printCLink02(LinkList L){
   printf(" %d ",L->data);
   LinkNode *pNode = L->next;
   while (pNode!=L)
   {
     printf(" %d ",pNode->data);
     pNode = pNode->next;
   }
   printf("\n");
   
}

//将循环单链表逆置
void reverseCLink(LinkList L){
   LinkNode *pCur = L->next;
   L->next = L;
   while (pCur!=L)
   {
      LinkNode *pNode = pCur;
      pCur = pCur->next;
      pNode->next = L->next;
      L->next = pNode;
   }
}
//将循环单链表左移k，此处用的是不带头结点的循环链表
void moveK(LinkList *L,int k){
   int cnt =0;
   LinkNode *pNode = *L;
   while (cnt < k)
   {
      pNode = pNode->next;
      cnt++;
   }
   (*L) = pNode;
   
}
//删除循环单链表的直接前驱
void deletePnodePre(LinkNode *p){
   LinkNode *pre = p;
   LinkNode *pCur = p->next;
   while (pCur->next !=p)
   {
     pre = pCur;
     pCur = pCur->next;
   }
   //找到了直接前驱
   pre->next = pCur->next;
   free(pCur);
}
//创建循环单链表的头结点
LinkNode* createClink(){
   LinkList L =  (LinkNode *)malloc(sizeof(LinkNode));
   (L)->next = (L);
}

void insertClink(LinkList L,LinkNode*pNode){
    pNode->next = L->next;
    L->next = pNode;
}
void splitCLink(LinkList L){
   LinkList charLink = createClink();
   LinkList numLink = createClink();
   LinkList otherLink = createClink();
   LinkNode *pCur = L->next;
   while (pCur!=L)
   {
      LinkNode* pNode = pCur;
      pCur = pCur->next;
      if(pNode->data > 'A' && pNode->data <'z'){
         insertClink(charLink,pNode);
      }else if(pNode->data > '0' && pNode->data <'9'){
         insertClink(numLink,pNode);
      }else{
         insertClink(otherLink,pNode);
      }
   }
   
}

//将单链表的第i号到第m号转为逆置的循环单链表
LinkList reverse(LinkList L,int i,int m){
      LinkNode *iPre = getPre(L,i);
      LinkNode *mPre = getPre(L,m);
      LinkNode *mLast = mPre->next->next;
      mPre->next->next = NULL;//方便进行遍历数据
      //拿到需要逆置的开始节点
      LinkNode *pNode = iPre->next;
      //删除i-m
      iPre->next = mLast;
      LinkList L2 = (LinkNode *)malloc(sizeof(LinkNode));
      (L2)->next = (L2);
      while (pNode!=NULL)
      {
         LinkNode *pCur = pNode;
         pNode = pNode->next;
         pCur->next = L2->next;
         L2->next = pCur;
      }
      return L2;
}
//将带头结点的循环单链表LA，Lb，长度分别为m,n,合并为一个循环单链表，时间复杂度最小
LinkList combineCLink(LinkList La,LinkList Lb,int m,int n){
   LinkNode * pCur = NULL;
   if(m > n){
      pCur = Lb->next;
      while (pCur !=Lb)
      {
         LinkNode* pNode = pCur;
         pCur = pCur->next;
         pNode->next = La->next;
         La->next = pNode;
      }
      free(pCur);
      return La;
   }else{
      pCur = La->next;
      while (pCur !=La)
      {
         LinkNode* pNode = pCur;
         pCur = pCur->next;
         pNode->next = Lb->next;
         Lb->next = pNode;
      }
      free(pCur);
      return Lb;
   }

}

//构建一个尾指针指向的循环单链表
void createCircleList02(LinkList *L,Elemtype arr[],int length){
      int cnt = 0;
      (*L) =  (LinkNode *)malloc(sizeof(LinkNode));
      (*L)->next = (*L);
      while (cnt < length)
      {
        LinkNode *pNode = (LinkNode *)malloc(sizeof(LinkNode));
        pNode->data = arr[cnt++];
        pNode->next = (*L)->next;
        (*L)->next = pNode;
        (*L) = pNode;
      }
}
//打印尾指针指向的循环单链表
void printCLink03(LinkList L){
   LinkNode *pHead = L->next;
   LinkNode *pNode = pHead->next;
   while (pNode!=pHead)
   {
     printf(" %d ",pNode->data);
     pNode = pNode->next;
   }
   printf("\n");
}
//设计新数据结构让合并循环单链表La，Lb效率尽量高
LinkList combineCLinkNewStruct(LinkList La,LinkList Lb){
   //使用尾指针指向的循环单链表来合并
   LinkNode *pAHead = La->next;
   LinkNode *pBHead = Lb->next;
   LinkNode* pNode = pAHead->next;

   La->next = pBHead->next;
   pBHead->next = pNode;
   free(pAHead);
}


typedef struct DuLinkNode{
   Elemtype data;
   struct DuLinkNode *pre;
   struct DuLinkNode *next;
}DuLinkNode,*DuLinkList;

//使得双链表的pre方向是一个升序
void order(DuLinkList Dul){
   DuLinkNode * pData = Dul->next;
   Dul->next = NULL;
   //从pre方向使用插入排序，pre方向从小到大  pre->pre == pcur
   while (pData!= NULL)
   { DuLinkNode *pNode = pData;
     pData = pData->next;
     DuLinkNode *pCur = Dul->pre ;
     DuLinkNode *pre = Dul;
     while (pCur !=NULL)
     {
      //移动指针寻找位置
      pre = pCur;
      pCur = pCur->pre;
     }
     //找到位置或者是本来就没有一个节点
     pNode->pre = pre->pre;// pCur
     pre->pre = pNode;
   }
}

//循环双链表分割并逆置

void reverseDulCiecleLink(DuLinkList L){
   DuLinkNode * pData = L->next;
   DuLinkNode * L2 = (DuLinkNode*)malloc(sizeof(DuLinkNode));
   L2->next = L2;
   L2->pre = L2;
   L->pre =L;
   L->next = L;
   DuLinkNode* pTail = L;
   int isEven = 0 ;// 0为奇数位，1为偶数位
   while (pData != L)
   {
     DuLinkNode *pNode = pData;
     pData = pData->next;
     if(isEven == 0){
         //尾插
         pNode->next = pTail->next;
         pTail->next = pNode;
         pNode->pre = pTail;
         pTail = pNode;
         isEven =1;
     }else{
         //头插
         pNode->next = L2->next;
         pNode->pre = L2;
         L2->next->pre = pNode;
         L2->next = pNode;
         isEven = 0;
     }
   }
   if(L2->next != L2){
      pTail->next = L2->next;
      L2->next->pre = pTail;
      L2->pre->next = L;
      L->pre = L2->pre;
   }
   
}
int main(){
  
   DuLinkList La = NULL,Lb = NULL;
   LinkList Lc=  NULL;
   int a[9] = {1,2,3,4,5,6,7,8,9};
   int b[6] = {1,2,3,4,5,6};
   int c[3] = {7,8,9};
   // createDuLlist(&La,a,9);
   // create(&Lb,b,6);
   // createCircleList02(&Lc,c,3);
   createDuLlist(&La,a,9);
   reverseDulLink(La);
   printCLink04(La);
  //printCLink03(Lc);
  
  
  
   
}